//
// Created by liushuai on 2021/2/9.
//

#include "reorderList.h"

// ListNode* mergeOrder(ListNode* head1,ListNode* head2){
//     if(head1&&head2){
//         ListNode* nextNode = head1->next;
//         head1->next = mergeOrder(head2,nextNode);
//     }
//     if(head1&&!head2){
//         return head1;
//     }
//     if(!head1&&head2){
//         return head2;
//     }
//     return head1;
// }
void reorderList(ListNode* head) {
  ListNode* fastNode = head;
  ListNode* slowNode = head;
  ListNode* preNode = nullptr;
  while (fastNode && fastNode->next) {
    preNode = slowNode;
    fastNode = fastNode->next->next;
    slowNode = slowNode->next;
  }

  ListNode* head1 = head;
  ListNode* head2 = reverseLinklist(slowNode);
  while (head1 && head2) {
    ListNode* nextNode1 = head1->next;
    ListNode* nextNode2 = head2->next;

    head1->next = head2;
    head1 = nextNode1;
    head2->next = head1;
    head2 = nextNode2;
  }
}